//字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 
//
// 
//
// 示例： 
//
// 
//输入：S = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca", "defegde", "hijhklij"。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
// 
//
// 
//
// 提示： 
//
// 
// S的长度在[1, 500]之间。 
// S只包含小写字母 'a' 到 'z' 。 
// 
// Related Topics 贪心 哈希表 双指针 字符串 
// 👍 604 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PartitionLabels {
    public static void main(String[] args) {
        new PartitionLabels().new Solution().partitionLabels("dccccbaabe");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 分不清是贪心还是dp
         * 我终于按照自己的思路做出来了，感动死我了
         * 其实一开始也是没头绪，瞥了一眼题解看到的两个指针就灵光乍现了
         * 具体实现：
         *  1.使用一个二维数组存储字符串中所有字符出现的起始位置和结束位置，不存在则置-1
         *  2.遍历字符串，得到字符出现的顺序
         *  3.使用start和end保存当前字符区间的开始和结束位置
         *  4.按照字符出现的顺序遍历二维数组
         *      如果num[0]>end，说明要更新区间了，先进行记录，再更新start和end
         *      否则更新end为end和num[1]中较大的那一个
         *  5.遍历结束后再进行一次记录
         *  优化了一下遍历时能做的事情，性能提高了一点点
         *  当然空间可以继续优化，只存储结束位置也可以
         */
        public List<Integer> partitionLabels(String s) {
            int[][] indexes = new int[26][2];//储存起止位置的数组
            List<Character> charList = new ArrayList<>();///顺序储存出现的字符的集合
            List<Integer> list = new ArrayList<>();//储存结果
            for (int[] nums : indexes) Arrays.fill(nums, -1);//首先给起止位置都赋-1
            for (int i = 0; i <s.length() ; i++) {
                //遍历字符串，这是时间复杂度最高的地方
                char c = s.charAt(i);
                if (!charList.contains(c)){//存储字符
                    charList.add(c);
                    indexes[c-'a'][0] = i;//更新起止位置坐标
                }
                indexes[c-'a'][1] = i;
            }
            int[] temp = indexes[s.charAt(0)-'a'];
            int start = temp[0];
            int end = temp[1];
            for (char c : charList){//遍历所有出现的字符
                int[] nums = indexes[c-'a'];
                if (nums[0] > end) {//这里说明当前字符已经超出了之前连续区间的范围，要进行更新了
                    list.add(end - start + 1);//记录长度
                    start = nums[0];//更新区间起止位置
                    end = nums[1];
                } else end = Math.max(end, nums[1]);//否则只更新区间结束位置
            }
            list.add(end-start+1);///在最后进行一次记录
            return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}